class Solution
{
public:
    bool canThreePartsEqualSum(vector<int> &arr)
    {
        int n = arr.size();
        vector<int> prefixSum(n + 1);
        prefixSum[0] = 0;
        partial_sum(arr.begin(), arr.end(), prefixSum.begin() + 1);
        if (prefixSum[n] % 3 != 0)
        {
            return false;
        }
        int subSum = prefixSum[n] / 3;
        int i = 1;
        for (; i <= n - 2; ++i)
        {
            if (prefixSum[i] == subSum)
            {
                break;
            }
        }
        if (prefixSum[i] != subSum)
        {
            return false;
        }
        int j = n - 1;
        for (; j > i; --j)
        {
            if (prefixSum[n] - prefixSum[j] == subSum)
            {
                break;
            }
        }
        if (prefixSum[n] - prefixSum[j] != subSum)
        {
            return false;
        }
        if (j == i)
        {
            return false;
        }
        return prefixSum[j] - prefixSum[i] == subSum;
    }
};